package LinkedList;//给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
//
// 
// 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 5 * 10⁴] 内 
// -10⁵ <= Node.val <= 10⁵ 
// 
//
// 
//
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 
//
// 
//
// 注意：本题与主站 148 题相同：https://leetcode-cn.com/problems/sort-list/ 
// Related Topics 链表 双指针 分治 排序 归并排序 👍 17 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class sortList {
    public static ListNode sortList(ListNode head) {
//        return mergeSort(head,null);
        return mergeSort(head);
    }

    //堆排序
    private static ListNode stackSort(ListNode head){
        if(head==null){
            return head;
        }
        PriorityQueue<Integer> listNodes = new PriorityQueue<>();
        ListNode h = head;
        while(h!=null){
            listNodes.add(h.val);
            h = h.next;
        }
        ListNode temp = new ListNode(0);
        ListNode res = temp;
        while(!listNodes.isEmpty()){
            int val = listNodes.poll();
            res.next = new ListNode(val);
            res = res.next;
        }
        return temp.next;
    }


    private static ListNode mergeSort(ListNode head, ListNode tail) {
        //无法继续拆分的情况
        if (head == null) {
            return null;
        }
        //无法继续拆分的情况
        if (head.next == tail) {
            head.next = null;
            return head;
        }

        //快慢指针找到中间节点
        ListNode slow = head, fast = head;
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow;
        //左边继续拆分
        ListNode left = mergeSort(head, mid);
        //右边继续拆分
        ListNode right = mergeSort(mid, tail);
        //有序链表合并
        return merge(left, right);
    }

    private static ListNode mergeSort(ListNode head) {
        //不可再分的情况，到达尾节点
        if(head.next == null){
            return head;
        }
        ListNode slow = head, fast = head, pre = head;
        while(fast!=null && fast.next!=null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //pre执行分段的末尾,//截断第一段
        pre.next = null;
        //slow是第二段的开头，head是第一段的开头
        ListNode l = mergeSort(head);
        ListNode r = mergeSort(slow);
        return merge(l,r);

    }

    private static ListNode merge(ListNode left, ListNode right) {
        ListNode mergeNode = new ListNode(0);
        ListNode help = mergeNode;
        //比较两个链表当前的值，值小的链表就把引用赋给mergeNode，并向后移动一位重新赋值给自己，同时help指向值小的那个节点
        while (left != null && right != null) {
            if (left.val < right.val) {
                help.next = left;
                left = left.next;
            } else {
                help.next = right;
                right = right.next;
            }
            help = help.next;
        }
        //最后如果有剩余的节点，就一次性链上去
        help.next = left == null ? right : left;
        return mergeNode.next;
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(0);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(4);
        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

//        ListNode listNode = sortList(node);
        ListNode listNode = stackSort(node);
        while(listNode!=null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)
